Analog audio or image signals are converted to digital form by “sampling,” i.e., repeatedly measuring the signal amplitude over time or over the image; the set of samples thus obtained constitutes a digital approximation of the initial signal and can be used to reproduce the signal. Decimation, or “downsampling,” is an operation in digital-signal or -image processing in which a set of samples is reduced in size. For example, a set of 100 samples may be decimated by a factor of two by selecting 50 samples that best represent the analog signal defined by the original 100 samples. The selection may be made by simply selecting every odd (or even) sample or, in more sophisticated operations, by replacing every pair of original samples with their average.
Because decimation reduces the effective sampling rate of the signal, however, care must be taken that the new sampling rate is at least twice the frequency of any components of interest within the original signal (the so-called Nyquist frequency). If the original signal included components with frequencies above the Nyquist frequency, they will be “aliased” and corrupt the components of interest in the sample set. An anti-aliasing filter may be used to remove these high-frequency components; in decimation operations, an averaging filter is commonly used as an anti-aliasing filter. An averaging filter outputs a pointy at a location n (i.e., the nth point y), given an input set of points x, by averaging N input points x for each output pointy. This operation is expressed formally in Equation (1)
                              y          n                =                              1            N                    ⁢                                                    ∑                                  k                  =                  n                                                            n                +                N                -                1                                      ⁢                          x              k                                                          (        1        )            
For example, if 10 input points x are averaged for each output pointy (N=10), then y0 is the average of x0 through x9, y1 is the average of x1 through x10, y2 is the average of x2 through x11, and so on. The sum needed for each new average may be computed by taking the value of the sum in the last average, subtracting the value of the “oldest” sample, and adding the value of the “newest” sample. For example, to compute the average of x1 through x10, the value of x0 is subtracted from the sum of x0 through x9 (which is already computed for the previous average), and the value of x10 is added. More formally, the sum of input points x from xn to xm is given below in Equation (2).
                              S                      n            ,            m                          =                              ∑                          k              =              n                        m                    ⁢                      x            k                                              (        2        )            The value of a “next” sum is therefore defined by Equation (3),S(n+1),(m+1)=Sn,m−xn+x(m+1)  (3)in which the distance between n and m is defined by N, and thus m=n+(N−1). For the sake of illustration, Equation (3) becomes, using the example above, the expression shown below in Equation (4).S1,10=S0,9−x0+x10  (4)In general, Equation (1) may be re-written as an average of computed sums, as shown below in Equation (5).
                              y          n                =                              1            N                    ⁢                      S                          n              ,              m                                                          (        5        )            
While this approach is attractive because it requires only one additional addition and subtraction operation per sample, it requires that the N−1 previous samples be stored in memory (because, at each new sample, the process must know the value of the “oldest” sample in order to subtract it). This memory requirement becomes even more severe in the case of operations such as raster-order image streaming, which requires the storage of N−1 previous lines of samples. The memory required for such storage may exceed the local storage space available to a processor, requiring the use of slower, system memory. In the worst case, the fetching and retrieval from system memory is too slow to keep up with the incoming data rate, and the filtering process fails. A need therefore exists for a decimation operation that has a lower memory requirement.